﻿//658. 找到 K 个最接近的元素
//给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
//整数 a 比整数 b 更接近 x 需要满足：
//| a - x | < | b - x | 或者  | a - x| == |b - x | 且 a < b



class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x)
    {
        //大于等于x的第一个位置
        auto right = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
        auto left = right - 1;
        vector<int> ans;
        while (k--)
        {
            if (right < arr.size() && left >= 0)
            {
                if (abs(arr[right] - x) < abs(arr[left] - x))
                {
                    right++;
                }
                else
                {
                    left--;
                }
            }
            else if (left < 0)
            {
                right++;
            }
            else
            {
                left--;
            }
        }
        return vector<int>(arr.begin() + left + 1, arr.begin() + right);
    }
};